package com.xinwei.leetcode.数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

// https://leetcode-cn.com/problems/merge-intervals/
public class _56_合并区间 {
    // 先把每个数组按照第一个的大小顺序进行排序，怎么排的好好学学
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (o1[0] - o2[0]);
            }
        });
        ArrayList<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);
        int[] right = intervals[0]; // 表示已经合并的最右边的数组
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= right[1]) {
                // 待合并的数组的左边小于已合并的数组的右边,合并
                right[1] = Math.max(right[1], intervals[i][1]);
                merged.set(merged.size() - 1, right);
            }else {
                // 待合并的数组的左边大于已合并的数组的右边，添加
                merged.add(intervals[i]);
                right = intervals[i];
            }
        }
        return merged.toArray(new int[merged.size()][2]);
    }
}
